/**
* @description: 838. 推多米诺
* @author hewei
* @date 2022/9/5 14:46
* @version 1.0
*/

public class PushDominoes {

    public String pushDominoes(String dominoes) {
        int max = Integer.MAX_VALUE;
        int n = dominoes.length();
        int[] l = new int[n];
        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            char c = dominoes.charAt(i);
            if (c == 'L') {
                r[i] = max;
            } else if (c == 'R') {
                r[i] = 1;
            } else {
                if (i == 0) {
                    r[i] = max;
                } else r[i] = r[i - 1] == max ? max : r[i - 1] + 1;
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            char c = dominoes.charAt(i);
            if (c == 'L') {
                l[i] = 1;
            } else if (c == 'R') {
                l[i] = max;
            } else {
                if (i == dominoes.length() - 1) {
                    l[i] = max;
                } else l[i] = l[i + 1] == max ? max : l[i + 1] + 1;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char c = dominoes.charAt(i);
            if (c == 'L' || c == 'R' || l[i] == r[i]) {
                stringBuilder.append(c);
            } else if (l[i] > r[i]) {
                stringBuilder.append('R');
            } else stringBuilder.append('L');
        }
        return stringBuilder.toString();
    }
}
